package com.yun.datastructure.linear.list.linkedlist.leetcode;

import com.yun.datastructure.linear.list.linkedlist.ListNode;

public class Leetcode141 {
    public boolean hasCycle(ListNode head) {
        ListNode p1=head;//龟
        ListNode p2=head;//兔
        while (p2!=null&&p2.next!=null){//当兔子走到链表尾部,或者兔子下一步走到链表尾部退出
            p1=p1.next;
            p2=p2.next.next;
            if(p1==p2){
                return true;
            }
        }
        return false;
    }

    public int point(ListNode head){
        ListNode p1=head;
        ListNode p2=head;
        while (p2!=null&&p2.next!=null){
            p1=p1.next;
            p2=p2.next.next;
            if(p1==p2){
                p1=head;
                break;
            }
        }
        int i=1;
        while (p1!=p2){
            p1=p1.next;
            p2=p2.next;
            i++;
        }
        return i;
    }

    public static void main(String[] args) {
        ListNode o7 = new ListNode(5, null);
        ListNode o6 = new ListNode(5, o7);
        ListNode o5 = new ListNode(5, o6);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        o7.next=o4;
        boolean n1 = new Leetcode141().hasCycle(o1);
        if(n1){
            System.out.println(new Leetcode141().point(o1));
        }
        System.out.println(n1);
    }
}
